1. Technical Field
The disclosed technology relates to the field of object-oriented compiler and run-time optimizations.
2. Background Art
Virtual dispatch in a single inheritance Object-Oriented-Programming (OOP) Runtime can be handled using the well-known v-table dispatch technique. However, Object Oriented Programming Runtimes that support multiple inheritance or a similar capability (such as the interface capability of the Java® programming environment) are more complex due to the conflicting name spaces for the members (such as class fields and/or methods) in the superclasses for a class C (the well-known diamond problem). The simplest solution is a quadratic table of all member holders in the system. However, these tables are subject to quadratic growth and are sparsely populated because most member holders are classes that inherit from very few member holders. A member holder can be, for example, a class/interface/type that contains members such as methods and/or fields. In the descriptions herein, specific references to classes, methods, fields, etc. are intended to serve as illustrations for the general case of members in holders. For example, a subclass of a superclass can have added members over the superclass. These added members in the subclass comprise the contribution for the subclass.
The problem is how to implement the following queries in object-oriented programming languages with multiple inheritance: 1) dynamic interface inheritance testing given multiple interface inheritance; 2) dynamic subclass testing given multiple implementation inheritance; 3) interface method invocation selection dispatch given multiple interface inheritance; and 4) method invocation selection dispatch given multiple implementation inheritance.
There has been significant research in achieving time/space/implementation effort tradeoffs for virtual dispatch. Many of the known techniques marginally improve the time or space aspect, but often with a very significant implementation and debugging effort. The two implementation extremes are: 1) recursive search in the holder hierarchy (excellent space efficiency but very slow); and 2) A quadratic table of size number-of-holders times number-of-potential-holders (provides excellent query speed, but the space requirement is quadratic with the number of holders). There exist many implementations between these extremes.
Extensive research has been documented about different approaches to method dispatch in Object-Oriented programming environments. For example, a comparison of the technology used in the area of dispatch tables with a competitive solution both in terms of space and speed was published in: Compact Dispatch Tables for Dynamically Typed Object Oriented Languages, Jan Vitek, R. Nigel Horspool, International Conference on Compiler Construction (CC 1996) and Efficient Type Inclusion Tests, Jan Vitek, R. Nigel Horspool, Andreas Krall, Conference on Object Oriented Programming Systems, Languages Applications (OOPSLA'97). These documents may assist one not skilled in the art with understanding the problem addressed by the technology disclosed herein.
For each new OOP languages (such as scripting languages) adding multiple inheritance capability generally requires many person-months or -years to implement and debug the above queries.
It would be advantageous to provide a virtual dispatch technology that is simple to implement yet has a speed/space tradeoff that is appropriate for general use.